package com.example.question.list;

import java.util.Random;

public class SimpleSkipList {
    // 头节点标记符
    private final static byte HEAD_BIT = (byte) -1;
    private final static byte TAIL_BIT = (byte) 1;
    private final static byte DATA_BIT = (byte) 0;


    private static class Node {
        private Integer value;
        private Node up, down, left, right;
        // 节点类型
        private byte bit;

        public Node(Integer value, byte bit) {
            this.value = value;
            this.bit = bit;
        }

        public Node(Integer value) {
            this(value, DATA_BIT);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", bit=" + bit +
                    '}';
        }
    }


    private Node head;
    private Node tail;
    private int size;
    private int height;
    private Random random; // 通过随机的方式决定元素应该放在第几层

    public SimpleSkipList() {
        this.head = new Node(null, HEAD_BIT);
        this.tail = new Node(null, TAIL_BIT);
        // 头结点的右边就是尾结点
        head.right = tail;
        // 尾结点的左边就是头结点
        tail.left = head;
        this.random = new Random(System.currentTimeMillis());
    }

    private Node find(Integer element) {
        // 从头结点开始寻找
        Node current = head;
        for (; ; ) {
            // 当前节点的右节点不是尾结点  当前节点的右节点的值小于element
            while (current.right.bit != TAIL_BIT && current.right.value <= element) {
                // 继续向右前行
                current = current.right;
            }
            // 当前节点存在down节点
            if (current.down != null) {
                // 开始向下一层
                current = current.down;
            } else {
                // 到达最底层，终止循环
                break;
            }
        }
        return current;
    }

    public void add(Integer element) {
        // 根据element找到合适他的存储位置，也就是临近的节点，
        // 需要注意的是，此刻该节点再整个跳表的第一层
        Node nearNode = find(element);
        // 定义一个新节点
        Node newNode = new Node(element);
        // 新节点的左边是nearNode
        newNode.left = nearNode;
        // 新节点的右节点为nearNode.right
        // 相当于将新节点插入到nearNode和nearNode.right中间
        newNode.right = nearNode.right;
        // 更新nearNode.right.left
        nearNode.right.left = newNode;
        nearNode.right = newNode;
        // 当前层级为0，代表第一层
        int currentLevel = 0;
        // 根据随机值判断是否将新的节点放到新的层级，在跳表算法描述中，该动作称为抛硬币
        while (random.nextDouble() < 0.5d) {

            if (currentLevel >= height) {
                // 为跳表增加一层链表
                height++;
                // 新层级的头结点和尾结点
                Node dummyHead = new Node(null, HEAD_BIT);
                Node dummyTail = new Node(null, TAIL_BIT);

                // 新层的head和tail的关系
                dummyHead.right = dummyTail;
                dummyHead.down = head;
                head.up = dummyHead;

                dummyTail.left = dummyHead;
                dummyTail.down = tail;
                tail.up = dummyTail;

                head = dummyHead;
                tail = dummyTail;
            }

            // 在新的一层增加element节点，同样要维护上下左右的关系
            // todo 这部分再研究一下
            while (nearNode != null && nearNode.up == null) {
                nearNode = nearNode.left;
            }

            nearNode = nearNode.up;
            Node upNode = new Node(element);
            upNode.left = nearNode;
            upNode.right = nearNode.right;
            upNode.down = newNode;
            nearNode.right.left = upNode;
            nearNode.right = upNode;
            newNode.up = upNode;
            newNode = upNode;
            currentLevel++;
        }
        // 元素个数自增
        size++;
    }

    public boolean contains(Integer element) {
        Node current = find(element);
        return current.value != null && current.value.equals(element);
    }

    public Integer get(Integer element) {
        Node node = find(element);
        return node.value.equals(element) ? node.value : null;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }


    public static void main(String[] args) {
        SimpleSkipList skipList = new SimpleSkipList();
        skipList.add(1);
        skipList.add(3);
        skipList.add(4);
        skipList.add(5);
        skipList.add(6);
        System.out.println(skipList.contains(5));
        System.out.println(skipList.get(5) == 5);
    }


}
